Sau khi ý định của Tổng thống Yeltsin tái lập Viktor Chernomyrdin làm thủ tướng Nga bị Duma ngăn cản tháng 9 năm 1998, tổng thống quay sang lựa chọn Primakov làm một nhân vật hứa hẹn và ông cho rằng sẽ dễ dàng được đa số nghị viện thông qua. Với tư cách thủ tướng, Primakov được công nhận vì đã thúc đầy một số cuộc cải cách vô cùng khó khăn ở Nga, đa số chúng, như cải cách thuế, trở thành một thành công lớn. Tuy quan điểm chống đối học thuyết Đơn cực của Hoa Kỳ của ông được biết đến với hầu hết người Nga, nó cũng dẫn tới một sự bất hoà mang tính thảm hoạ với phương Tây trong chiến dịch của NATO tại Kosovo, khiến nước Nga bị cô lập hoàn toàn trong những phát triển sau đó của Nam Tư cũ.

Các nhà phân tích quy việc cách chức Primakov ngày 12 tháng 5 năm 1999 của Yeltsin là một phản ứng trước lo ngại mất quyền lực vào tay một nhân vật thành công và được biết đến nhiều hơn. Primakov cũng từ chối cách chức các bộ trưởng Cộng sản khi Đảng Cộng sản Liên bang Nga lãnh đạo quá trình chuẩn bị buộc tội tổng thống không thành công. Tuy nhiên, Yeltsin đã từ chức vào cuối năm đó và được kế tục bởi thủ tướng đương thời, Vladimir Putin.

Ngày 24 tháng 3 năm 1999, Primakov đi tới Washington, D.C. trong một chuyến thăm chính thức. Khi bay qua Đại Tây Dương, ông biết rằng NATO đã bắt đầu ném bom Nam Tư. Primakov quyết định huỷ bỏ chuyến thăm, và ra lệnh cho máy bay quay đầu trên biển trở về Moskva - nó đã được gọi là cú lộn Primakov.[9]